\section{Vorlesung am 10.10.2012: Wahrscheinlichkeit, perfekte Geheimhaltung und der DES-Algorithmus}

\subsection{Perfekte Geheimhaltung}

In dieser Vorlesung betrachten wir den Begriff der perfekten Geheimhaltung, allerdings ohne den Beweis von Theorem 5.4.3. Daher gehen wir auf die grundlegenden Begriffe der Wahrscheinlichkeitstheorie in \buchmann{5.1 und 5.2} nicht näher ein.

\buchmann{5.4}
%
Das Ziel ist es, ein Kryptosystem zu definieren, bei dem selbst ein (passiver) Angreifer mit \emph{unbegrenzten (!) Ressourcen}  nicht in der Lage ist, aus Kenntnis des Chiffrats sowie der Wahrscheinlichkeitsverteilung auf $\mathcal{P}$ Informationen über den Klartext zu erhalten. Ein solches Kryptosystem heißt auch \emph{unconditionally secure} (im Gegensatz zu \emph{computationally secure}, d.h.\ dass für das zugrunde liegende Problem kein effizienter Algorithmus bekannt ist) oder \emph{informations-theoretisch sicher}.

Ein Kryptosystem heißt \emph{perfekt geheim}, wenn $\forall p \in \mathcal{P} \: \forall c \in \mathcal{C} \: : \: Pr(p|c) = Pr(p)$, d.h.\ dass die Wahrscheinlichkeit für das Auftreten eines bestimmten Klartextes bei gegebenem Chiffrat genauso groß ist, wie die Wahrscheinlichkeitsverteilung auf $\mathcal{P}$ angibt. Ein Angreifer erlangt durch die Kenntnis von $c$ also keinen Vorteil, um bestimmte Klartexte als unwahrscheinlich auszusondern.

Seien $|\mathcal{P}| = |\mathcal{C}| = |\mathcal{K}| < \infty$ und $Pr(p) > 0$ für alle Klartexte $p$. Der Satz von \textsc{Shannon}†besagt, dass das Kryptosystem perfekt geheim ist gdw.\ jeder Schlüssel gleich wahrscheinlich ist, d.h.\ $Pr(k) = 1/|\mathcal{K}|$, und es gilt $\forall p \in \mathcal{P} \: \forall c \in \mathcal{C} \: \exists_1 k \in \mathcal{K} \: : \: c = E_k(p)$.

\subsection{Das Vernam-One-Time-Pad}
\buchmann{5.5} 
%
Beim One-Time-Pad von \textsc{Vernam} ist $\mathcal{P} = \mathcal{C} = \mathcal{K} = \{ 0, 1 \}^n$ und $E_k(p) = p \oplus k$, wobei $\oplus$ bitweises XOR meint. Der Schlüssel $k$ ist gemäß Gleichverteilung aus dem Menge aller Bitstrings der Länge $n$ zu wählen. Für alle $p \in \mathcal{P}$ und $c \in \mathcal{C}$ gibt es genau einen Schlüssel (nämlich $k = p \oplus c$), der die beiden ineinander überführt.

Das OTP hat gewisse Nachteile: jeder Schlüssel muss so lange sein wie die Nachricht, er darf nur einmal verwendet werden, aktive Angriffe, bei denen einzelne Bits gezielt geändert werden können, sind möglich (solange nicht durch zusätzliche Maßnahmen die Authentizität gesichert wird).  

\subsection{Zufallszahlen und Pseudozufallszahlen}
\buchmann{5.6 und 5.7} 
%
``Echte'' Zufallsbits können mit speziellen Hardware-Modulen (die z.B.\ radioaktiven Zerfall messen), Standard-Hardware (Auswertung von Luftturbulenzen in der Festplatte, Rauschen am Audio-Eingang) oder  in Software (Benutzerverhalten) erzeugt werden. Einen Zufallszahlengenerator für gleichverteilte nichtnegative ganzzahlige Werte kleiner oder gleich $m$ erhält man dadurch, dass man $n = \lfloor \log_2 m \rfloor + 1$ Zufallsbits $b_1 \ldots b_n$ erzeugt und Ergebnisse $\sum_{i=1}^n b_i 2^{n-i}$ größer $m$ verwirft. Zufallszahlen mit $n$ Bit Länge erhält man über die Binärdarstellung mit führender $1$ und $n-1$ zufälligen folgenden Stellen.

Ein Pseudozufallszahlengenerator (pseudo random number generator, PRNG) erzeugt auf Basis eines \emph{Seed} (Startwert) eine Folge von Zufallsbits, die mit polynomiellem Aufwand nicht von einer ``echten'' Zufallsfolge unterschieden werden kann. Schlüsselstromgeneratoren sind solche PRNGs.


\subsection{Feistel-Chiffren}
\buchmann{6.1}
%
Der Einsatz des Data Encryption Standard (DES) ist aufgrund seiner für heutige Verhältnis\-se zu kurzen Schlüssellänge zwar nicht mehr empfehlenswert, allerdings findet sich das dahinter stehende Konstruktionsprinzip einer \emph{Feistel-Chiffre} (auch Feistel-Netzwerk genannt) bei einigen neueren Kryptosystemen (z.B.\ Blowfish) wieder.

Für eine Feistel-Chiffre ist $\mathcal{P} = \mathcal{C} = \{ 0, 1 \}^{2t}$. Die Verschlüsselungsfunktion $E_k$ arbeitet auf Klartextblöcken $p = (L_0, R_0)$, die man in eine linke und rechte Hälfte jeweils der Länge $t$ teilen kann. Es werden $r$ \emph{Runden} mit jeweils identischer Berechnung bei jeweils wechselndem \emph{Rundenschlüssel} (round key, auch: subkey) $K_i$ wie folgt berechnet:
$(L_1,R_1) = (R_0, L_0 \oplus f_{K_1}(R_0)), \ldots (L_i,R_i) = (R_{i-1}, L_{i-1} \oplus f_{K_i}(R_{i-1}))$.
Die Rundenschlüssel werden dabei per \emph{key scheduling}†aus dem Schlüssel $k$ abgeleitet.
$E_k(p) = E_k(L_0, R_0)$ ist dann das Ergebnis $(L_r, R_r)$ der letzten Runde. $E_k$ kann invertiert werden, ohne die Funktion $f$ selbst zu invertieren: $(R_{i-1}, L_{i-1}) = (L_i, R_i \oplus f_{K_i}(L_i))$. Die Entschlüsselung kann berechnet werden, indem man dieselben  Rundenoperationen wie bei der Verschlüsselung auf $(R_r, L_r)$ (Chiffretext mit vertauschter linker und rechter Hälfte) anwendet, jedoch die Reihenfolge der Rundenschlüssel umkehrt. Man erhält damit $(R_0, L_O)$.

% auf http://en.wikipedia.org/wiki/Feistel_cipher
% wird $(R_n, L_n)$ als Chiffrat genommen, daher fällt das Vertauschen vor der Entschlüsselung weg !

% auf http://de.wikipedia.org/wiki/Feistelchiffre
% wird $(L_n, R_n)$ als Chiffrat genommen


\subsection{Der DES-Algorithmus}
\buchmann{6.2}
%
DES ist intern aus folgenden Komponenten aufgebaut:
\begin{itemize}
\item Der in der Feistel-Chiffre verwendeten Funktion $f$, welche aus einer  \emph{Expansionsfunktion} $E: \{0,1\}^{48} \rightarrow \{0,1\}^{32}$, einer Bitpermutation $P: \{0,1\}^{32} \rightarrow \{0,1\}^{32}$ und acht \emph{S-Boxen} $S_i : \{0,1\}^{6} \rightarrow \{0,1\}^{4}$ aufgebaut ist und bei der eine XOR-Veknüpfung mit einem 48 Bit langen Teilschlüssel erfolgt. Expansionsfunktion, Bitpermutation und S-Boxen sind schlüsselunabhängig.

\item
Eine initiale Permutation $\mathrm{IP} : \{0,1\}^{64} \rightarrow \{0,1\}^{64}$, bei der es sich um eine feste Bitpermutation handelt. Vor den $16$ Runden der Feistel-Chiffre wird $\mathrm{IP}$ und danach $\mathrm{IP}^{-1}$ angewandt.

{\small Diese Bitpermutation hat keine kryptographische Bedeutung und geht vermutlich auf eine Optimierung der Speicherzugriffe der zum Entwurfszeitpunkt in der 1970er Jahren verwendeten Datenbusse mit $8$ Bit Breite zurück.
Am Ende wird $\mathrm{IP}^{-1}$ angewandt, damit die Konstruktion gewissermaßen \emph{selbstinvers}\footnote{Eine Abbildung $f : X \rightarrow X$ heißt selbstinvers (oder auch: ``involutorisch'') gdw.\ $\forall x \in X : f(f(x)) = x$.)} ist: Die Entschlüsselung kann erfolgen, indem derselbe Algorithmus mit der umgekehrten Reihenfolge der Rundenschlüssel ausgeführt wird.}

\item
Key Scheduling-Verfahren zur Ableitung von $48$ Bit langen Rundenschlüssel aus dem DES-Schlüssel mit $56$ Bit Länge. Dabei werden Abbildungen $\mathrm{PC1} :\{ 0, 1 \}^{64} \rightarrow \{ 0, 1 \}^{28} \times \{ 0, 1 \}^{28}$ und $\mathrm{PC2} : \rightarrow \{ 0, 1 \}^{28} \times \{ 0, 1 \}^{28} \rightarrow \{ 0, 1 \}^{48}$ verwendet (``PC'' steht hier für ``permuted choice''). DES-Schlüssel werden auch als Bitstring der Länge $64$ geschrieben, wobei dann jedes achte Bit ein Prüfbit ist (ungerade Parität).
\end{itemize}

Für einen Rundenschlüssel $K \in \{ 0, 1\}^{48}$, eine rechte Hälfte $R \in \{ 0, 1\}^{32}$ wird $f_k(R) \in \{ 0, 1\}^{32}$ wie folgt berechnet: expandiere $R$ mit $E$ auf $48$ Bit, verknüpfe das Ergebnis XOR mit $K$, wende die S-Boxen an, um wieder einen Bitstring der Länge $32$ Bit zu erhalten, der gemäß $P$ einer Bitpermutation unterworfen wird.

Bezeichnet man die durch die S-Boxen $S_1, \ldots, S_8$ definierte Abbildung als $S : \{0,1\}^{48} \rightarrow \{0,1\}^{32}, B_1 \ldots B_8 \mapsto S_1(B_1) \ldots S_8(B_8)$ mit Blöcken $B_i$ der Länge $6$, so lautet als geschlossene Formel $f_K(R) = P(S(E(R) \oplus K))$.

{\small Nach Anwendung der Expansionsfunktion erscheinen 16 der 32 Bits von $R$ doppelt in $E(R)$, aber niemals im selben $6$-Bit-Block. Die Expansion erhöht also die Diffusion, da manche Bits der Eingabe zwei Bits der Ausgabe beeinflussen.}

Die S-Boxen werden über Tabellen-Lookups realisiert. Für jeden $6$-Bit-Block von $E(R) \oplus K$ wird eine andere Abbildung verwendet. Sie sind die einzige nicht-lineare Funktion bei DES und sorgen für Konfusion. Wären die S-Boxen ebenfalls linear, so könnte man ein lineares Gleichungssystem aufstellen und nach den Schlüsselbits auflösen.

{\small Die Design-Kriterien der S-Boxen bei DES wurden zunächst nicht offen gelegt, weshalb spekuliert worden war, dass es eine ``Hintertür'' oder bewusste Schwäche gibt, die der amerikanische Technikgeheimdienst NSA (National Security Agency) ausnutzen könnte. Mittlerweile weiß man, dass DES als besonders widerstandsfähig gegen differentielle Kryptoanalyse, die der NSA lange im voraus bekannt war, entworfen wurden.}

Die Bitpermutation $P$ sorgt wiederum für Diffusion, da die Ausgabe-Bits einer S-Box innerhalb des $32$ Bit langen Zustands so umgeordnet werden, dass sie in der nächsten Runde mehrere S-Boxen beeinflussen.

Beim Key Scheduling werden zunächst aus dem (als Bitstring der Länge $64$ dargestellten) Schlüssel $k$ mittels $\mathrm{PC1}$ zwei jeweils $28$ Bit lange Hälften $(C_0, D_0) = \mathrm{PC1}(k)$ erzeugt. Effektiv wird dabei nur eine Bitpermutation auf dem Schlüssel ohne die Paritätsbits ausgeführt. Die Rundenschlüssel werden als $K_i = \mathrm{PC2}(C_i,D_i)$ berechnet, wobei $C_i$ aus $C_{i-1}$ durch einen zirkulären Linksshift um 1 oder 2 Positionen (je nach $i$) ermittelt wird. $D_i$ erhält man analog aus $D_{i-1}$.

{\small Im Ergebnis enthalten alle Rundenschlüssel $48$ Bits der (effektiv) $56$ Bits von $k$ in geänderter Reihenfolge. Jedes Bit von $k$ wird in durchschnittlich $14$ der $16$ Runden von DES verwendet.}


\subsection{Mehrfachverschlüsselung}

\buchmann{4.7} Eine größere effektive Schlüssellänge und damit höhere Sicherheit gegen Brute-Force-Angriffe kann man erreichen, indem man ein Chiffrat $c = E_{k_1}(m)$ ein- oder mehrmals erneut verschlüsselt: $c' = E'_{k_2}(c), c'' = E''_{k_3}(c'), \ldots$. Dabei können die Verschlüsselungsverfahren $E, E', E'', \ldots$ identisch oder unterschiedlich sein. Der Schlüssel vergrößert sich entsprechend auf $k_1 \parallel k_2 \parallel k_3 \ldots$.

Bei einer Blockchiffre mit $\mathcal{K} = \{ 0, 1 \}^{n}$ führt interessanterweise die nahe liegende zweifache Ausführung der Chiffre $m \mapsto E_{k_2}(E_{k_1}(m))$ nicht zu einer effektiven Verdoppelung der Schlüssellänge von $n$ auf $2n$. Grund dafür ist der \emph{Meet-in-the-Middle-Angriff}. Diese Known-Plaintext-Attacke auf ein Paar $\left(m, c= E_{k_2}(E_{k_1}(m))\right)$ funktioniert wie folgt: Der Angreifer verschlüsselt $m$ mit allen möglichen $k \in \mathcal{K} = \{ 0, 1 \}^n$ und legt sich eine Tabelle mit Einträgen $\{ (E_k(m), k) : k \in \mathcal{K} \}$ an. Das Chiffrat $c$ wird mit allen möglichen $k' \in \mathcal{K}$ entschlüsselt, bis $D_{k'}(c)$ mit einem Eintrag $E_k(m)$ in der Tabelle übereinstimmt. Dann gilt $D_{k'}(c) = E_k(m)$, d.h.\ $c = E_{k'}(E_k(m))$ und $k \parallel k'$ ist gleich $k_1 \parallel k_2$ (oder zumindest ein guter Kandidat, der noch mit anderen Klartext/Chiffrat-Paaren getestet werden kann). Im Vergleich zu dem Brute-Force-Angriff auf den Schlüssel $k_1 \parallel k_2 \in \mathcal{K} \times \mathcal{K} = \{ 0, 1\}^{2n}$, welcher einen Aufwand von $O(2^{2n})$ besitzt, ist der Aufwand für einen Meet-in-the-Middle-Angriff erheblich geringer. Für die Berechnung und Speicherung der Tabelle sind die Aufwände jeweils $O(2^n)$. Die Entschlüsselungen $D_{k'}$ haben einen Rechenaufwand von $O(2^n)$.
Insgesamt ergibt sich ein Rechenaufwand für meet-in-the-middle von $O(2^n + 2^n) = O(2^{n+1})$ im Vergleich zu $O(2^{2n})$. Der doppelt so lange Schlüssel bringt also lediglich $1$ Bit Sicherheitsgewinn (wobei für den Angriff natürlich Speicher von $O(2^n)$ erforderlich ist).

Da die Schlüssellänge von $56$ beim DES-Algorithmus angesichts heutiger Rechenpower zu kurz ist, sollte DES nur mit dreifacher Anwendung verwendet werden, typischerweise geschieht dies wie folgt: $\mathrm{3DES}_{k_1 \parallel k_2 \parallel k_3}(m) = E_{k_3}(D_{k_2}(E_{k_1}(m)))$, wobei $D=E^{-1}$ die Entschlüsselungsfunktion ist. Dies hat den Vorteil der ``Abwärts\-kompatibilität'': mit $k_2 = k_3 = $ beliebig ist $\mathrm{3DES}_{k_1 \parallel k_2 \parallel k_3}(m) = \mathrm{DES}_{k_1}(m)$. Falls $k_1, k_2, k_3$ unabhängig gewählt werden, hat man 168, falls $k_3 = k_1$ gesetzt wird, eine effektive Schlüssellänge von 112 Bit. Man spricht von 2-Key bzw.\ 3-Key Triple-DES (3DES, auch: DESede für ``DES encrypt-decrypt-encrypt'').

{\small 
Weniger gebräuchlich, von der Sicherheit her aber gleichwertig, ist aufgrund geringerer Flexibilität die \emph{EEE}-Konstruktion $E_{k_3}(E_{k_2}(E_{k_1}(m)))$ bei DES mit 168 Bit Schlüssellänge. }


\subsection{Key Whitening ${\star}$}
Eine Verstärkung einer Blockchiffre $E_k : \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^n$ kann durch \emph{Key Whitening} erreicht werden. Der Schlüssel $k$ wird dabei verlängert zu $k \parallel k_1 \parallel k_2$, wobei $k_1, k_2 \in \{ 0, 1 \}^{n}$. 

Ein Klartext $m$ wird verschlüsselt, indem er zunächst mit $k_1$ und das Ergebnis der Blockchiffren-Anwendung mit $k_2$ XOR-verknüpft werden.
\[
  m \mapsto E_k(m \oplus k_1) \oplus k_2
\]

Die Konstruktion ist dadurch motiviert, dass der Angreifer kein Klar-/Chiffretext-Paar für die zugrunde liegende Blockchiffre $E_k$ erhält. Die Widerstandsfähigkeit gegen Brute-Force-Angriffe (allerdings nicht gegen analytische Angriffe) wird mit geringem Aufwand von zwei XOR-Operationen deutlich erhöht. 

{\small Bei DESX ist $E_k = \mathrm{DES}_k$ und es wird durch Whitening der Schlüssel auf $120 (=56+64)$ Bit verlängert. Der DES-Schlüssel $k$ (mit $56$ Bit) und $k_1$ werden frei gewählt und $k_2$ aus ihnen über eine Einwegfunktion berechnet.}
